

class Solution {
    public int minPathSum(int[][] grid) {
        int m=grid.length;
        int n=grid[0].length;

        int[][] dp=new int[m+1][n+1];
        dp[0][0]=grid[0][0];

        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                if(i==0&&j==0) continue;
                if(i==0) dp[i][j]=dp[i][j-1]+grid[i][j];
                else if(j==0) dp[i][j]=dp[i-1][j]+grid[i][j];
                else dp[i][j]=Math.min(dp[i-1][j],dp[i][j-1])+grid[i][j];
            }
        }
        return dp[m-1][n-1];
    }
}

class Solution1 {
    public int calculateMinimumHP(int[][] dungeon) {
        int m = dungeon.length;
        int n = dungeon[0].length;
        int[][] dp = new int[m][n];

        // 从右下角开始计算
        dp[m - 1][n - 1] = Math.max(1, 1 - dungeon[m - 1][n - 1]);

        // 填充最后一列
        for (int i = m - 2; i >= 0; i--) {
            dp[i][n - 1] = Math.max(1, dp[i + 1][n - 1] - dungeon[i][n - 1]);
        }

        // 填充最后一行
        for (int j = n - 2; j >= 0; j--) {
            dp[m - 1][j] = Math.max(1, dp[m - 1][j + 1] - dungeon[m - 1][j]);
        }

        // 填充其余部分
        for (int i = m - 2; i >= 0; i--) {
            for (int j = n - 2; j >= 0; j--) {
                int minRequired = Math.min(dp[i + 1][j], dp[i][j + 1]);
                dp[i][j] = Math.max(1, minRequired - dungeon[i][j]);
            }
        }

        return dp[0][0];
    }

    public static void main(String[] args) {
        System.out.println(-0x3fffffff);
    }
}


class Solution2 {
    public int maxSubArray(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0; // 如果数组为空，返回 0 或其他默认值
        }

        int maxSum = nums[0]; // 全局最大子数组和
        int currentSum = nums[0]; // 当前子数组和

        for (int i = 1; i < nums.length; i++) {
            // 决定是继续扩展当前子数组，还是从当前元素重新开始
            currentSum = Math.max(nums[i], currentSum + nums[i]);
            // 更新全局最大子数组和
            maxSum = Math.max(maxSum, currentSum);
        }

        return maxSum;
    }
}